package BackTrackingPackage2;

import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

/**
 * @author Lzm
 * @version 1.0
 */
public class combinationSum2_ {

  List<Integer> list = new ArrayList<>();
  List<List<Integer>> result = new ArrayList<>();
  @Test
  public void combinationSum2Test(){
    int[] candidates = new int[]{10,1,2,7,6,1,5};
    combinationSum2(candidates,8);
    for (List<Integer> integers : result) {
      System.out.println(integers.toString());
    }
  }

  public List<List<Integer>> combinationSum2(int[] candidates, int target) {
    Arrays.sort(candidates);
    backTracking(candidates,target,0);
    return result;
  }

  public void backTracking(int[] candidates,int target, int startIndex){
    if (getSum(list) == target){
      result.add(new ArrayList<>(list));
      return;
    }
    if (getSum(list) > target){
      return;
    }
    for (int i = startIndex ; i < candidates.length ; i ++){
      if (i > startIndex && candidates[i] == candidates[i - 1]){
        continue;
      }
        list.add(candidates[i]);
        backTracking(candidates,target,i+1);
        list.remove(list.size() - 1);
    }
  }
  public int getSum(List<Integer> path){
    int sum = 0;
    if (path.size() != 0 && path != null){
      for (Integer integer : path) {
        sum += integer;
      }
    }
    return sum;
  }
}
